package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         170,
		Discription: "交易逆序对的个数",
		Level:       3,
		Labels: map[string]int{
			"归并排序":  1,
		},
	})
}


func ReversePairs(record []int) int {
	count := 0
	var merge func([]int)
	merge = func(nums []int) {
		if len(nums) <= 1 {
			return
		}

		n := len(nums)
		mid := n / 2
		leftNums := append([]int(nil), nums[:mid]...)
		rigthNums := append([]int(nil), nums[mid:]...)
		merge(leftNums)
		merge(rigthNums)

		k := 0
		i := 0
		j := 0
		rightCount := 0
		for k < n {
			if i >= mid {
				nums[k] = rigthNums[j]
				k++
				j++
				continue
			}

			if j >= n-mid {
				nums[k] = leftNums[i]
				i++
				k++
				count += rightCount
				continue
			}

			if leftNums[i] <= rigthNums[j] {
				nums[k] = leftNums[i]
				i++
				count += rightCount
			} else {
				nums[k] = rigthNums[j]
				j++
				rightCount++
			}
			k++
		}
	}

	merge(record)
	return count
}